<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>03_插入排序</title>
  </head>
  <body>
    <script>
      /* 插入排序 */
      function insertionSort(arr) {
        // 1.获取数组的长度
        const length = arr.length
        // 2.外层循环: 外层循环是从1位置开始, 依次遍历到最后
        for (let i = 1; i < length; i++) {
          // 3.记录取出的元素, 放在变量temp中用于插入比较
          let j = i
          let temp = arr[i]
          // 4.内层循环: 内层循环不确定循环的次数, 最好使用while循环
          while (j > 0 && arr[j - 1] > temp) {
            // 将前一项后移
            arr[j] = arr[j - 1]
            j--
          }
          // 5.将选出的j位置, 放入temp元素
          arr[j] = temp
        }
        return arr
      }
      var arr = [3, 5, 1, 4, 2]
      console.log(insertionSort(arr))
    </script>
  </body>
</html>
